package com.yulan.Tree;



import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 104. 二叉树的最大深度
 */
public class LeetCode_104 {



    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        else{
            int left_hight = maxDepth(root.left);
            int right_height = maxDepth(root.right);
            return Math.max(left_hight,right_height)+1;
        }
    }

    public int maxDepth_Stack(TreeNode root){
        Queue<Pair<TreeNode,Integer>> stack = new LinkedList<>();
        if(root!=null){
            stack.add(new Pair<>(root,1));
        }

        int depth = 0;
        while(!stack.isEmpty()){
            Pair<TreeNode,Integer> current = stack.poll();
            TreeNode curNode = current.getKey();
            int cur_dep = current.getValue();
            if(root!=null){
                depth = Math.max(depth,cur_dep);
                if(curNode.left!=null) stack.add(new Pair<>(curNode.left,cur_dep+1));
                if(curNode.right!=null) stack.add(new Pair<>(curNode.right,cur_dep+1));
            }
        }
        return depth;
    }

}
